class Solution {
    static class TreeNode {
        public int val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return isBalancedChild(root) != -1;
    }
    private int isBalancedChild(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftH = isBalancedChild(root.left);
        int rightH = isBalancedChild(root.right);
        int ret = Math.abs(leftH-rightH);
        if(ret <= 1 && leftH >= 0 && rightH >= 0){
            return Math.max(leftH,rightH) + 1;
        }else{
            return -1;
        }
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot == null){
            return true;
        }
        if(root == null){
            return false;
        }
        if(isSame(root,subRoot)){
            return true;
        }
        return isSubtree(root.left, subRoot)||
        isSubtree(root.right, subRoot);
    }

    private boolean isSame(TreeNode root, TreeNode subRoot){
        if(root == null && subRoot == null){
            return true;
        }
        if(root == null || subRoot == null){
            return false;
        }
        if(root.val != subRoot.val){
            return false;
        }

        return isSame(root.left,subRoot.left) && isSame(root.right,subRoot.right);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        if(isSame2(root.left, root.right)){
            return true;
        }
        return false;
    }

    private boolean isSame2(TreeNode rootLeft, TreeNode rootRight){
        if (rootRight == null && rootLeft == null){
            return true;
        }
        if(rootRight == null || rootLeft == null){
            return false;
        }
        if(rootRight.val != rootLeft.val){
            return false;
        }
        return isSame2(rootLeft.right, rootRight.left) && isSame2(rootLeft.left, rootRight.right);
    }

    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        if(root.left == null && root.right == null){
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    int pre = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pre = postorder.length-1;
        return buildTreeChild(inorder, postorder, 0, inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] inorder, int[] postorder, int inBegin, int inEnd){
        if( inBegin > inEnd ){
            return null;
        }
        TreeNode root = new TreeNode(postorder[pre]);
        int inorderIndex = findInorderIndex(inorder, postorder[pre], inBegin, inEnd);
        pre--;
        root.right = buildTreeChild(inorder, postorder, inorderIndex+1, inEnd );
        root.left = buildTreeChild(inorder, postorder, inBegin, inorderIndex-1);
        return root;
    }

    private int findInorderIndex(int[] inorder, int val, int inBegin, int inEnd){
        for (int i = inBegin; i <= inEnd ; i++) {
            if(inorder[i] == val){
                return i;
            }
        }
        return -1;
    }

    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();

        tree2strChild(root, stringBuilder);
        return stringBuilder.toString();
    }

    private void tree2strChild(TreeNode cur, StringBuilder stringBuilder){
        if(cur == null){
            return;
        }
        stringBuilder.append(cur.val);
        if(cur.left != null){
            stringBuilder.append('(');
            tree2strChild(cur.left, stringBuilder);
            stringBuilder.append(')');
        }else {
            if(cur.right == null){
                return;
            }else{
                stringBuilder.append("()");
            }
        }
        if(cur.right != null){
            stringBuilder.append('(');
            tree2strChild(cur.right, stringBuilder);
            stringBuilder.append(')');
        }else{
            return;
        }
    }
}